home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / DCLAP 6d / dclap6d / network / nsclilib / ni_list.c < prev    next >
Text File  |  1996-07-05  |  15KB  |  484 lines
  1. /*      
  2. * ===========================================================================
  3. *
  4. *                            PUBLIC DOMAIN NOTICE                          
  5. *               National Center for Biotechnology Information
  6. *                                                                          
  7. *  This software/database is a "United States Government Work" under the   
  8. *  terms of the United States Copyright Act.  It was written as part of    
  9. *  the author's official duties as a United States Government employee and 
  10. *  thus cannot be copyrighted.  This software/database is freely available 
  11. *  to the public for use. The National Library of Medicine and the U.S.    
  12. *  Government have not placed any restriction on its use or reproduction.  
  13. *                                                                          
  14. *  Although all reasonable efforts have been taken to ensure the accuracy  
  15. *  and reliability of the software and data, the NLM and the U.S.          
  16. *  Government do not and cannot warrant the performance or results that    
  17. *  may be obtained by using this software or data. The NLM and the U.S.    
  18. *  Government disclaim all warranties, express or implied, including       
  19. *  warranties of performance, merchantability or fitness for any particular
  20. *  purpose.                                                                
  21. *                                                                          
  22. *  Please cite the author in any work or product based on this material.   
  23. *
  24. * ===========================================================================
  25. *
  26. * File Name:    ni_list.c
  27. *
  28. * Author:       Beatty, Gish
  29. *
  30. * Version Creation Date:        1/1/92
  31. *
  32. * $Revision: 4.0 $
  33. *
  34. * File Description: 
  35. *   List and ring management functions.
  36. *
  37. *
  38. * Modifications:  
  39. * --------------------------------------------------------------------------
  40. * Date     Name        Description of modification
  41. * -------  ----------  -----------------------------------------------------
  42. * 4/23/92  Epstein     Added extensive in-line commentary, and removed all tabs
  43. * 5/11/92  Epstein     Changed ListSwapAdj() to provide more rigorous testing
  44. *                      that its two arguments are adjacent in the list.
  45. * 5/14/92  Epstein     Added ListStrCopy() and ListStrDel()
  46. * 7/06/92  Epstein     Fixed bug in ListStrCopy(), where the newly created
  47. *                      list was not being returned to the caller ... whoops.
  48. *
  49. * ==========================================================================
  50. *
  51. *
  52. * RCS Modification History:
  53. * $Log: ni_list.c,v $
  54.  * Revision 4.0  1995/07/26  13:56:32  ostell
  55.  * force revision to 4.0
  56.  *
  57.  * Revision 1.2  1995/05/17  17:52:27  epstein
  58.  * add RCS log revision history
  59.  *
  60. */
  61.  
  62. #include "ni_list.h"
  63.  
  64.  
  65.  
  66. /*
  67.  * Purpose:     Insert an item as the next element in a doubly linked list(ring)
  68.  *
  69.  * Parameters:
  70.  *   elem           Next element to be inserted; this is data only,not a NodePtr
  71.  *   ap             Insertion point
  72.  *
  73.  * Returns:
  74.  *                The newly allocated NodePtr, containing forward and backward
  75.  *                pointers and a pointer to elem
  76.  *
  77.  *
  78.  * Description:
  79.  *              Allocate the necessary memory for a "Node", attach the
  80.  *              caller's data to that Node, and insert the Node after the
  81.  *              specified node in the list, maintaining the integrity of
  82.  *              a doubly-linked ring. If there are no other items in the
  83.  *              ring, create a "minimal" ring which consists of the single
  84.  *              Node pointing to itself in both directions.
  85.  *
  86.  * Note:
  87.  *              Most "list" data is actually stored in a doubly-linked ring, as
  88.  *              shown below. Furthermore, note that each node only contains a
  89.  *              pointer to the actual data in the list, rather than the actual
  90.  *              data itself.
  91.  *
  92.  *          +------------------------------------------------------------------+
  93.  *          ^                                                                  |
  94.  *          |       +-------------------------------------------------------+  |
  95.  *          |       |                                                       ^  |
  96.  *          |       V                                                       |  |
  97.  *          |   +-------+       +-------+                       +-------+   |  |
  98.  *          |   | next  |------>| next  |------> ...    ------->| next  |-->+  |
  99.  *          |   +-------+       +-------+                       +-------+      |
  100.  *          +<--| last  |<------| last  |<------ ...    <-------| last  |<-----+
  101.  *              +-------+       +-------+                       +-------+
  102.  *              | elem  |       | elem  |                       | elem  |
  103.  *              +-------+       +-------+                       +-------+
  104.  *                  |               |                               |
  105.  *                  |               |                               |
  106.  *                  V               V                               V
  107.  *              +-------+       +-------+                       +-------+
  108.  *              | actual|       | actual|                       | actual|
  109.  *              | data  |       | data  |                       | data  |
  110.  *              +-------+       +-------+                       +-------+
  111.  */
  112.  
  113. NodePtr 
  114. ListInsert(VoidPtr elem, NodePtr ap)                     /* ptr to node to insert after */
  115. {
  116.     NodePtr             np;
  117.     
  118.     if (elem == NULL)
  119.         return NULL;
  120.     
  121.     np = (NodePtr) MemNew(sizeof(Node));
  122.     np->elem = elem;
  123.     
  124.     if (ap == NULL) {           /* no nodes in list */
  125.         np->last = np;
  126.         np->next = np;
  127.         return np;
  128.     }
  129.     else {                              /* 1 or more nodes in list */
  130.         np->next = ap->next;
  131.         ap->next = np;
  132.         np->next->last = np;
  133.         np->last = ap;
  134.         return np;
  135.     }
  136. } /* ListInsert */
  137.  
  138.  
  139.  
  140. /*
  141.  * Purpose:     Insert an item as the previous element in a doubly linked
  142.  *              list(ring)
  143.  *
  144.  * Parameters:
  145.  *   elem           Next element to be inserted; this is data only,not a NodePtr
  146.  *   ap             Insertion point
  147.  *
  148.  * Returns:
  149.  *                The newly allocated NodePtr, containing forward and backward
  150.  *                pointers and a pointer to elem
  151.  *
  152.  *
  153.  * Description:
  154.  *              Insert the specified item into the ring, before the specified
  155.  *              insertion point. In the case where the specified insertion
  156.  *              point was NULL, this is equivalent to ListInsert().
  157.  */
  158.  
  159. NodePtr 
  160. ListInsertPrev(VoidPtr elem, NodePtr ap)                     /* ptr to node to insert before */
  161. {
  162.     NodePtr             np;
  163.     
  164.     np = ap;
  165.     if (ap != NULL)
  166.         ap = ap->last;          /* previous node */
  167.     
  168.     ap = ListInsert(elem, ap);
  169.     return (np == NULL) ? ap : np;
  170. } /* ListInsertPrev */
  171.  
  172.  
  173.  
  174. /*
  175.  * Purpose:     Delete a single node from a list or ring
  176.  *
  177.  * Parameters:
  178.  *   np             Node to be deleted
  179.  *
  180.  * Returns:
  181.  *                A pointer to the "next" node in the list/ring, after the
  182.  *                deleted node.
  183.  *
  184.  *
  185.  * Description:
  186.  *              Delete the specified node from a list or ring. It is the
  187.  *              responsibility of the caller to free the memory associated
  188.  *              with the "elem" (data), if appropriate.
  189.  */
  190.  
  191. NodePtr 
  192. ListDelete(NodePtr np)
  193. {
  194.     NodePtr             nextnode, lastnode;
  195.     
  196.     if (np == NULL)
  197.         return NULL;
  198.     
  199.     nextnode = np->next;
  200.     lastnode = np->last;
  201.     
  202.     if (nextnode == NULL && lastnode == NULL)   /* only node in a list */
  203.         ;
  204.     else if (nextnode == NULL) {                /* last in a list */
  205.         np->last->next = NULL;
  206.         nextnode = np->last;
  207.     }
  208.     else if (lastnode == NULL) {                /* first in a list */
  209.         np->next->last = NULL;
  210.         nextnode = np->next;
  211.     }
  212.     else if (np == nextnode)                    /* last in a ring */
  213.         nextnode = NULL;
  214.     else {                                      /* node with both neighbors */
  215.         np->last->next = nextnode;
  216.         np->next->last = np->last;
  217.     }
  218.     
  219.     MemFree(np);                        /* assumes element memory has been freed */
  220.     return nextnode;
  221. } /* ListDelete */
  222.  
  223.  
  224.  
  225. /*
  226.  * Purpose:     Get the next element from a list or ring (non-destructively)
  227.  *
  228.  * Parameters:
  229.  *   np             Node before the node to be selected
  230.  *
  231.  * Returns:
  232.  *                A pointer to the "next" node in the list/ring (or NULL
  233.  *                if the list/ring was NULL). Note that for a list, the
  234.  *                returned value can also be NULL.
  235.  *
  236.  *
  237.  * Description:
  238.  *              Return the "next" node in the list or rin.g
  239.  */
  240.  
  241. NodePtr 
  242. ListGetNext(NodePtr np)
  243. {
  244.     if (np == NULL)
  245.         return NULL;
  246.     return np->next;
  247. } /* ListGetNext */
  248.  
  249.  
  250.  
  251. /*
  252.  * Purpose:     Swap two adjacent nodes in a list or ring
  253.  *
  254.  * Parameters:
  255.  *   np1            "Prior" node
  256.  *   np2            "Next" node
  257.  *
  258.  *
  259.  * Description:
  260.  *              Swap the two specified elements, provided that they are
  261.  *              adjacent, and np1 precedes np2.
  262.  */
  263.  
  264. void 
  265. ListSwapAdj(NodePtr np1, NodePtr np2)       /* priornode, nextnode */
  266. {
  267.     if (np1 == NULL || np2 == NULL || np1->next->last != np1) /* must be sane */
  268.         return;
  269.  
  270.     if (np1->next != np2 || np2->last != np1)             /* must be in order */
  271.         return;
  272.     
  273.     if (np1->last != NULL)
  274.         np1->last->next = np2;
  275.     
  276.     if (np2->next != NULL)
  277.         np2->next->last = np1;
  278.     
  279.     np1->next = np2->next;
  280.     np2->last = np1->last;
  281.     
  282.     np1->last = np2;
  283.     np2->next = np1;
  284. } /* ListSwapAdj */
  285.  
  286.  
  287.  
  288. /*
  289.  * Purpose:     Sort the specified ring/list
  290.  *
  291.  * Parameters:
  292.  *   head           Head of the list to be sorted
  293.  *   cmpfunc        Comparison function (return values are like memcmp())
  294.  *   order          ASCEND or DESCEND
  295.  *
  296.  * Returns:
  297.  *              A pointer to the first element of the sorted ring or list
  298.  *
  299.  *
  300.  * Description:
  301.  *              Sort the specified list, in place, using bubble sort, and
  302.  *              the specified comparison function. Determine prior to sorting
  303.  *              whether this is a list or a ring. If it's a ring, break the
  304.  *              ring prior to sorting, and restore it to a ring topology
  305.  *              after sorting has been completed.
  306.  */
  307.  
  308. NodePtr 
  309. ListSort(NodePtr head, int (*cmpfunc )PROTO ((NodePtr, NodePtr )), int order)                                  /* 0 if equal, LT 0 if 1st element > 2nd element */
  310. {
  311.     NodePtr             np;
  312.     Boolean             sorted = FALSE, ring;
  313.     int         result;
  314.     
  315.     if (head == NULL)
  316.         return NULL;
  317.     if (head->last == NULL)
  318.         ring = FALSE;
  319.     else
  320.         ring = TRUE;
  321.     if (ring)
  322.         ListBreakRing(head);
  323.     
  324.     /* just bubble sort for now */
  325.     
  326.     while (! sorted) {
  327.         np = head;
  328.         sorted = TRUE;
  329.         
  330.         while (np->next != NULL) {
  331.             result = (*cmpfunc)(np, np->next);
  332.             if ((result > 0 && order == ASCEND) || (result < 0 && order == DESCEND)) {
  333.                 sorted = FALSE;
  334.                 if (np == head)
  335.                     head = np->next;    /* keep head pointing at 1st element */
  336.                 ListSwapAdj(np, np->next);
  337.             }
  338.             else
  339.                 np = np->next;
  340.         }
  341.     }
  342.     
  343.     if (ring)
  344.         ListConnectRing(head);
  345.     return head;        /* ptr to first element */
  346. } /* ListSort */
  347.  
  348.  
  349.  
  350. /*
  351.  * Purpose:     Break the specified ring into a non-circular (linear) list
  352.  *
  353.  * Parameters:
  354.  *   np             Head of the ring to be broken
  355.  *
  356.  *
  357.  * Description:
  358.  *              Break the specified ring between its head and tail.
  359.  *
  360.  * Note:
  361.  *              This function may be called safely (without effect) if the
  362.  *              passed parameter is already a list, rather than a ring.
  363.  */
  364.  
  365. void 
  366. ListBreakRing(NodePtr np)
  367. {
  368.     if (np == NULL)
  369.         return;
  370.     if (np->last == NULL)
  371.         return;
  372.     
  373.     np->last->next = NULL;
  374.     np->last = NULL;
  375. } /* ListBreakRing */
  376.  
  377.  
  378.  
  379. /*
  380.  * Purpose:     Convert a list into a ring.
  381.  *
  382.  * Parameters:
  383.  *   head           Head of the list to be connected
  384.  *
  385.  *
  386.  * Description:
  387.  *              Connect the specified list between its head and tail, producing
  388.  *              a ring.
  389.  *
  390.  * Note:
  391.  *              This function may be called safely (without effect) if the
  392.  *              passed parameter is already a ring, rather than a list.
  393.  */
  394.  
  395. void 
  396. ListConnectRing(NodePtr head)
  397. {
  398.     NodePtr     np;
  399.     
  400.     if (head == NULL)
  401.         return;
  402.     
  403.     np = head;
  404.     
  405.     while (np->next != NULL) {
  406.         np = np->next;
  407.         if (np == head)
  408.             return;
  409.     }
  410.     
  411.     np->next = head;
  412.     head->last = np;
  413. } /* ListConnectRing */
  414.  
  415.  
  416. /*
  417.  * Purpose:     Copy a list where the list elements are character strings
  418.  *
  419.  * Parameters:
  420.  *   strlist        List to be copied
  421.  *
  422.  * Returns:
  423.  *              A copy of the original list (which may be NULL)
  424.  *
  425.  *
  426.  * Description:
  427.  *              Create a list which is a copy of the original list, and
  428.  *              also make copies of the strings.
  429.  *
  430.  * Note:
  431.  *              There is no obvious way to make a generic list copying
  432.  *              routine, because, in general, the length of each list
  433.  *              element is unknown. This is a simple case where it is
  434.  *              easy to copy a list.
  435.  */
  436.  
  437. NodePtr
  438. ListStrCopy (NodePtr strlist)
  439. {
  440.     NodePtr newlist = NULL;
  441.     NodePtr np = strlist;
  442.     CharPtr stringtext;
  443.  
  444.     if (strlist == NULL)
  445.         return NULL;
  446.  
  447.     do {
  448.         stringtext = StringSave((CharPtr) np->elem);
  449.         newlist = ListInsert(stringtext, newlist);
  450.         np = ListGetNext(np);
  451.     } while (np != NULL && np != strlist);
  452.  
  453.     return newlist->next; /* points to 1st element in new list */
  454. }
  455.  
  456.  
  457. /*
  458.  * Purpose:     Delete a list where the list elements are character strings
  459.  *
  460.  * Parameters:
  461.  *   np             List to be deleted
  462.  *
  463.  *
  464.  * Description:
  465.  *              Delete the list nodes and the character string data associated
  466.  *              with each node.
  467.  *
  468.  * Note:
  469.  *              This routine will work for any list element which is a single
  470.  *              block of memory. However, it will not work in the more general
  471.  *              case where a list element in turn references other memory
  472.  *              which must also be freed.
  473.  */
  474.  
  475. void
  476. ListStrDel (NodePtr np)
  477. {
  478.     while (np != NULL)
  479.     {
  480.         MemFree (np->elem);
  481.         np = ListDelete(np);
  482.     }
  483. }
  484.